package algorithm;

import java.util.Scanner;

/**
 * create by yongli on 2021-02-28 11:17
 */

public class MergeSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        int[] temp = new int[n];
        for(int i= 0;i<n;i++){
          arr[i]= scanner.nextInt();
        }

        mergeSort(arr,0,n-1,temp);
        for(int i=0;i<n;i++) {
            System.out.println(arr[i]+" ");
        }
    }
    public static void mergeSort(int[] arr,int l,int r, int[] temp){
        if (l >=r) return;

        int mid = (l + r) /2;
        mergeSort(arr,l,mid,temp);
        mergeSort(arr,mid+1,r,temp);
        int k=0,i=l,j=mid+1;
        while (i<=mid && j <=r){
            // i++和++i对于代码可读性的改进，一味的冗长不好，
            if (arr[i]> arr[j]){
                temp[k] = arr[j];
                j++;
            }else {
                temp[k] = arr[i];
                i++;
            }
            k++;
        }
        while (i<=mid){
            temp[k] = arr[i];
            i++;
            k++;
        }
        while (j<=r){
            temp[k] = arr[j];
            k++;
            j++;
        }
        for(int idx=0;idx<k;idx++) {
            arr[l+idx] = temp[idx];
        }

    }
}
